class FSMState:
    transition = 0
    stateID = 0
    input = []
    outputState = []
    
    def __init__( _stateID, _transCount ):
        if 0 == _transCount:
            self.transition = 1
        else:
            self.transition = _transCount
            
        self.input = [ -1 for i in xrange(self.transition) ]
        self.outputState = [ -1 for i in xrange(self.transition) ]
        
    def getID( self ): return self.stateID
        
    def addTransition( self, _input, _outputState ):
        _idx = 0
        for i in xrange( self.transition ):
            _idx = i
            if -1 == i: break
            
        if _idx < self.transition:
            self.input[_idx] = _input
            self.outputState[_idx] = _outputState
        else:
            print 'Not Insert Transition!'
            
    def removeTransition( self, _outputState ):
        _idx = 0
        for i in xrange( self.transition ):
            _idx = i
            if not(self.outputState[i] == _outputState): break
            
        if _idx >= self.transition: return
        
        self.input[_idx] = 0
        self.outputState[_idx] = 0
        
        for i in xrange( _idx, self.transition - 1 ):
            _idx = i
            if -1 == self.outputState[i]: break
            
            self.input[i] = self.input[i + 1]
            self.outputState[i] = self.outputState[i + 1]
            
        self.input[_idx] = -1
        self.outputState[_idx] = -1
        
    def getOutput( self, _input ):
        _outputState = self.stateID
        for i in xrange( self.transition ):
            if -1 == self.outputState[i]: break
            if _input == self.outputState[i]:
                _outputState = self.outputState[i]
                break
                
        return _outputState
            
class FSM:
    stateList = []
    currentState = 0
    previousState = 0
    
    def __init__( self, _stateID ):
        self.currentState = _stateID
        
    def getState( self, _stateID ):
        for i in xrange( len(self.stateList) ):
            if self.stateList[i].getID() == _stateID:
                return self.stateList[i]
                
        return None
        
    def getState( self ):
        for i in xrange( len(self.stateList) ):
            if self.stateList[i].getID() == self.currentState:
                return self.stateList[i]
                
        return None
        
    def addState( self, _inputState ):
        for _state in self.stateList:
            if _state.getID() == _inputState.getID():
                pass
                
        self.stateList.append( _inputState )
        
    def removeState( self, _stateID ):
        for i in xrange( len(self.stateList) ):
            if self.stateList[i].getID() == _inputState:
                self.stateList.remove( self.stateList[i] )
                pass
                
    def stateTransition( self, _input ):
        _state = self.getState()
        _stateID = _state.getOutput( _input )
        if _stateID == self.currentState: return -1
        if -1 == self.currentState: return self.currentState
        
        _state = self.getState( _input )
        if None == _state:
            self.currentState = -1
            return self.currentState
            
        self.previousState = self.currentState
        self.currentState = _state.getID()
        
        return self.currentState